package t_1356

import "sort"

func sortByBits(arr []int) []int {
	// 按二进制包含1的个数排序
	sortByBinary(arr)
	return arr
}

func sortByBinary(arr []int) {

	sort.Slice(arr, func(i, j int) bool {
		a, b := countBits(arr[i]), countBits(arr[j])
		// 当个数相同 按数值自然排序asc
		if a == b {
			return arr[i] < arr[j]
		}
		// 当个数不同 按个数自然排序asc
		return a < b
	})

}

func countBits(n int) int {
	count := 0
	for n != 0 {
		count += n & 1
		n >>= 1
	}
	return count
}
